package com.c0809;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author mwl
 * @date 2018-08-09
 * <p>
 * https://leetcode.com/problems/add-two-numbers/description/
 * You are given two non-empty linked lists representing two non-negative Longs. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
 * <p>
 * You may assume the two numbers do not contain any leading zero, except the number 0 itself.
 * <p>
 * Example:
 * <p>
 * Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
 * Output: 7 -> 0 -> 8
 * Explanation: 342 + 465 = 807.
 * <p>
 * 问题主要集中在，链接是否同样的长度，
 * </p>
 **/
public class Solution {
    public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        // 找不到 BigDecimal 类
        BigDecimal i1 = BigDecimal.ZERO;
        BigDecimal i2 = BigDecimal.ZERO;
        BigDecimal i = BigDecimal.ONE;
        BigDecimal j = BigDecimal.ONE;
        while (l1 != null) {
            i1 = i1.add(i.multiply(new BigDecimal(l1.val)));
            i = i.multiply(new BigDecimal(10));
            l1 = l1.next;
        }
        while (l2 != null) {
            i2 = i2.add(j.multiply(new BigDecimal(l2.val)));
            j = j.multiply(new BigDecimal(10));

            l2 = l2.next;
        }
        String result = i1.add(i2).toString();
        ListNode lr = new ListNode(result.charAt(0) - 48);
        for (int k = 1; k < result.length(); k++) {
            ListNode tmp = new ListNode(result.charAt(k) - 48);
            tmp.next = lr;
            lr = tmp;

        }

        return lr;
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        StringBuffer i1 = new StringBuffer();
        StringBuffer i2 = new StringBuffer();

        while (l1 != null) {
            i1.append(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            i2.append(l2.val);
            l2 = l2.next;
        }

        int cout = 0;
        ListNode lr = null;
        ListNode lr1 = null;
        for (int k = 0; k < i1.length() || k < i2.length() || cout > 0; k++) {
            int t1 = 0;
            int t2 = 0;
            if (k < i1.length()) {
                t1 = i1.charAt(k) - 48;
            }
            if (k < i2.length()) {
                t2 = i2.charAt(k) - 48;
            }
            int result = t1 + t2 + cout;
            cout = result / 10;
            ListNode tmp = new ListNode(result % 10);
            if (lr == null) {
                lr = tmp;
                lr1 = tmp;
            } else {
                lr1.next = tmp;
                lr1 = tmp;
            }
        }
        return lr;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    // 已知最大深度
    int maxDepth = 0;
    Integer result = 0;

    public static String defangIPaddr(String address) {
        return address.replaceAll("\\.", "[.]");
    }

    public static int numberOfSteps(int num) {
        int i = 0;
        while (num > 0) {
            if (num % 2 == 0) {
                num = num / 2;
            } else {
                num--;
            }
            i++;
        }
        return i;
    }

    public static int[] decompressRLElist(int[] nums) {
        int length = 0;
        for (int i = 0; i < nums.length; ) {
            length = length + nums[i];
            i = i + 2;
        }
        int[] result = new int[length + 2];
        int index = 0;
        for (int i = 0; i < nums.length; ) {
            int feq = nums[i];
            int val = nums[i + 1];
            for (int j = 0; j < feq; j++) {
                result[index++] = val;
            }
            i = i + 2;
        }
        return result;
    }

    public static int subtractProductAndSum(int n) {
        int product = 1;
        int sum = 0;
        while (n > 0) {
            int t = n % 10;
            n = n / 10;
            product = product * t;
            sum = sum + t;
        }
        return product - sum;

    }

    public static int[] smallerNumbersThanCurrent(int[] nums) {
        int result[] = new int[nums.length];
        int numCount[] = new int[101];
        int numLessCount[] = new int[101];
        for (int num : nums) {
            numCount[num] = numCount[num] + 1;
        }
        numLessCount[0] = 0;
        for (int i = 1; i < 101; i++) {
            numLessCount[i] = numLessCount[i - 1] + numCount[i - 1];
        }
        for (int i = 0; i < nums.length; i++) {
            result[i] = numLessCount[nums[i]];
        }

        return result;
    }

    public static int findNumbers(int[] nums) {
        int result = 0;
        for (int num : nums) {
            int tmp = num;
            while (tmp >= 100) {
                tmp /= 100;
            }
            if (tmp > 9) {
                result++;
            }
        }
        return result;
    }

    public static void main(String args[]) {
        Solution solution = new Solution();
        //TreeNode node = new TreeNode(3);
        //node.left = new TreeNode(2333);
        //node.right = new TreeNode(133333);
        //int result = solution.deepestLeavesSum(node);

        //for (int i = 0; i < 30; i++) {
        //    System.out.println("n=" + i + "-" + solution.fib(i) + "-" + solution.fib2(i));
        //}
        System.out.println(solution.countBits(2));
        System.out.println("ID".charAt(0) == 'I');
    }

    public int maxIncreaseKeepingSkyline(int[][] grid) {
        if (grid.length == 1) {
            return 0;
        }
        int length = grid.length;
        int result = 0;
        int rowMax[] = new int[length];
        int colMax[] = new int[length];
        // 取出行和列的最大值
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                if (grid[i][j] > rowMax[i]) {
                    rowMax[i] = grid[i][j];
                }
                if (grid[i][j] > colMax[j]) {
                    colMax[j] = grid[i][j];
                }
            }
        }
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                if (colMax[j] > rowMax[i]) {
                    result += rowMax[i] - grid[i][j];
                } else {
                    result += colMax[j] - grid[i][j];
                }

            }
        }
        return result;
    }

    public TreeNode insertIntoBST(TreeNode root, int val) {
        dfs2(root, val);
        return root;
    }

    private void dfs2(TreeNode node, int val) {
        if (val > node.val) {
            if (node.right == null) {
                node.right = new TreeNode(val);
            } else {
                dfs2(node.right, val);
            }
        } else {
            if (node.left == null) {
                node.left = new TreeNode(val);
            } else {
                dfs2(node.left, val);
            }
        }
    }

    public int deepestLeavesSum(TreeNode root) {
        // 当前节点深度
        int depth = 1;

        dfs(root, depth);
        return result;
    }

    private void dfs(TreeNode node, int depth) {
        System.out.println(result.toString());
        if (node == null) {
            return;
        }
        if (depth > maxDepth) {
            maxDepth = depth;
            result = node.val;
        } else if (depth == maxDepth) {
            result += node.val;
        }
        dfs(node.left, depth + 1);
        dfs(node.right, depth + 1);
    }

    public int[] createTargetArray(int[] nums, int[] index) {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < index.length; i++) {
            list.add(index[i], nums[i]);
        }
        int result[] = new int[index.length];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }

    public int[] createTargetArray2(int[] nums, int[] index) {
        int[] result = new int[nums.length];
        Arrays.fill(result, -1);
        for (int i = 0; i < index.length; i++) {
            if (!(result[index[i]] == -1)) {
                for (int j = result.length - 1; j > index[i]; j--) {
                    result[j] = result[j - 1];
                }
            }
            result[index[i]] = nums[i];
        }
        return result;
    }

    public int fib(int N) {
        if (N == 0) {
            return 0;
        }
        if (N == 1) {
            return 1;
        }
        return fib(N - 1) + fib(N - 2);
    }

    public int fib2(int N) {
        double phi = ((1 + Math.sqrt(5)) / 2);

        return (int) (Math.round(Math.pow(phi, N) / Math.sqrt(5)));
    }

    public int[] countBits(int num) {
        int[] result = new int[num + 1];
        for (int i = 0; i <= num; i++) {
            int j = i;
            j = (j & 0x55555555) + ((j >> 1) & 0x55555555);
            j = (j & 0x33333333) + ((j >> 2) & 0x33333333);
            j = (j & 0x0f0f0f0f) + ((j >> 4) & 0x0f0f0f0f);
            j = (j & 0x00ff00ff) + ((j >> 8) & 0x00ff00ff);
            j = (j & 0x0000ffff) + ((j >> 16) & 0x0000ffff);
            result[i] = j;
        }
        return result;

    }
    public int[] diStringMatch(String S) {
        int N = S.length();
        int result[] = new int[N + 1];
        int max = N;
        int min = 0;
        for (int i = 0; i < N; i++) {
            if (S.charAt(i) == 'I') {
                result[i] = min;
                min++;
            } else if (S.charAt(i) == 'D') {
                result[i] = max;
                max--;

            }
        }
        result[N] = min;

        return result;
    }

}

class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    TreeNode(int x) {
        val = x;
    }

}